Content addressable memory, known as CAM, are memory structures used to store similar pieces of data, or to store data that are frequently used in certain parts of computer programs. These data are stored in the CAM either with no particular order, or in the order in which they were previously used by the computer program. When an operating computer program reaches a step where a particular piece of data is needed, the program first asks if the required data is present in the CAM. The data in the CAM is sorted through, a process known as a sieve, and if data match is found, then the program does not have to take the time to go to the main memory to fetch the data. This results in a large time savings, and thus faster program operation.
Typically it is not the data itself that is sieved and matched, but a shorter summarization of the data, known as a tag. It is easier to sieve and match the short tags and thus the size of the content addressable memory can be reduced. The tag is associated with a specific element in a cache memory that holds the data. Thus CAM memories are useful in computers, and numerous CAM memories are found in most typical modern microprocessors and computer systems.
An example of the use of a CAM is found in memory testing. In the testing of a random access memory (RAM) device, several different types of tests will be done, and it may be interesting to know how many different locations on the RAM are defective. It would confuse the data to have the same RAM location, for example column 3 and row 4, listed as defective two or three different times. Thus the testing sequence might be to exercise the RAM with what is known as a rippling ones test, and find that location 3, 4 fails. This is stored in the CAM. The next test might be a rippling zeros test which also finds location 3,4 defective. The CAM is examined and the location 3,4 is found by matching and thus the rippling zeros test is not recorded as a new failure. Next, there may be a checkerboard test done which finds location 3,4 and location 15,1 failing. Matching both locations against the CAM will result in finding location 3,4 already in the memory and location 15,1 a new failure location, which is then recorded. Thus two distinct locations are found and recorded as failures from the three tests, versus the four failures which would have resulted from the two bad locations over the three tests.
It is well known how to test memories for proper functionality. Typical memory types such as random access memory (RAM) may be tested by writing a logic high, or a one into each memory location in turn, and reading that memory location value to check if a one is written there. The same thing is done by writing a logical low or zero. These two tests determine if any particular bit of the RAM is stuck either high or low. Frequently a checkerboard of alternating ones and zeros is written and read to test the memory. The checkerboard pattern is particularly useful for finding single RAM bit elements that have leakage paths to adjacent RAM elements, something which is not truly tested by the ones or zeros tests where the voltage level may remain high because the adjacent cell to which a leak exists is also high. There also exist tests which write a one into a memory of all zeros, and `walks` the one value through the memory. The comparable walking zero test is also well known in the art.
While the described testing process may be sufficient to completely test RAMs, it is not sufficient for completely testing CAMs, because a CAM is accessed by means of a compare of each of a number of individual bits that make up the tag that is stored in the CAM. Thus a CAM test must test not only that what is written into the CAM, i.e., the stuck-at tests described above, but also that the compare bits work as well. Some CAMs also have a wild card feature which allows matching to selected parts of the entire word. As a result of these features, it is more difficult in general to test CAMs than other types of devices.
It is also much more difficult to test a memory that is built into a logic or microprocessor device. This is known as an embedded memory. This is because in the embedded memory case, not all of the inputs to the memory are accessible to the tester. In general, none of the memory inputs are accessible since only the microprocessor ever needs to write or read from the embedded memory, and input pads are almost always in short supply due to the large increase in device size required for additional input pads. Thus, it is known to be difficult to design tests for embedded memories which will sufficiently test the memory function by exercising the microprocessor alone.
It is known in the art to add some circuitry to the embedded memory to allow what is known as a built-in self test, or BIST. The addition of BIST does add some increased area to the silicon device, but much less than the addition of input and output pads, and it also results in reduced testing difficulty and improved testing fault coverage. BIST is becoming very common in the art for testing various memory types such as RAM, ROM and FIFO, but BIST for CAMs present more difficult problems than for the other memory types, because CAMs have different operating modes than other memory types. Specifically, CAMs have to be tested for the ability to compare or match a test data value with different data values and find the correct data value stored in the CAM. For additional information on BIST for CAMs, see U.S. Pat. No. 5,107,501 by Yervant Zorian, issued Apr. 21, 1992. However, prior art BIST for CAMs requires that the CAM have an additional read port, bus and circuitry added to each cell of the CAM, which adds area to the silicon device. Additionally, the BIST testing of CAMs has controllability and observability problems even with the additional circuitry, read ports and buses, because the propagation logic needed to transport the CAM output to an observability point such as an output pad is long and complex.
Therefore, it would solve a problem in the art to provide a built-in self test mechanism that is simple, adds less cost to the silicon device, and provides better precision in verifying the location of the CAM defect.